// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ssa

// fuseBranchRedirect检查一个CFG，其中一个If块的出站分支
// 可以从其前一个If块派生，在
// 某些情况下，我们可以直接将前一个If块重定向到对应的后一个
// 块。例如：
// p:
// v11=Less64<bool>v10 v8 
// 。。。
// v17=Leq64<bool>v10 v8 
// 。
// 
// 这里的实现借用了prove pass的框架。
// 1，遍历函数f的所有块以找到If块。
// 2，对于任何If块b，遍历其所有前辈以查找If块。
// 3，对于任何If块前置p，更新关系p->b。
// 4，遍历b的所有后续。
// 5，对于b的任何后续s，尝试更新关系b->s，如果发现
// 矛盾，则将p重定向到b的另一个后继项。
func fuseBranchRedirect(f *Func) bool {
	ft := newFactsTable(f)
	ft.checkpoint()

	changed := false
	for i := len(f.Blocks) - 1; i >= 0; i-- {
		b := f.Blocks[i]
		if b.Kind != BlockIf {
			continue
		}
		// b为空或仅包含控制值。
		// TODO:如果b只包含OpCopy或OpNot related to b.控件，
		// 例如Copy（Not（Copy（Less64（v1，v2））），或许可以对其进行优化。
		bCtl := b.Controls[0]
		if bCtl.Block != b && len(b.Values) != 0 || (len(b.Values) != 1 || bCtl.Uses != 1) && bCtl.Block == b {
			continue
		}

		for k := 0; k < len(b.Preds); k++ {
			pk := b.Preds[k]
			p := pk.b
			if p.Kind != BlockIf || p == b {
				continue
			}
			pbranch := positive
			if pk.i == 1 {
				pbranch = negative
			}
			ft.checkpoint()
			// 假设分支p->b被占用。
			addBranchRestrictions(ft, p, pbranch)
			// 根据上述条件检查是否有任何传出分支无法访问。
			parent := b
			for j, bbranch := range [...]branch{positive, negative} {
				ft.checkpoint()
				// 尝试更新关系b->child，并检查是否出现矛盾。
				addBranchRestrictions(ft, parent, bbranch)
				unsat := ft.unsat
				ft.restore()
				if !unsat {
					continue
				}
				// 此分支不可能，因此请将p直接重定向到另一个分支。
				out := 1 ^ j
				child := parent.Succs[out].b
				if child == b {
					continue
				}
				b.removePred(k)
				p.Succs[pk.i] = Edge{child, len(child.Preds)}
				// 将b中的Phi值设置为少一个参数。
				for _, v := range b.Values {
					if v.Op != OpPhi {
						continue
					}
					b.removePhiArg(v, k)
					phielimValue(v)
				}
				// 安排孩子多生一个前任。
				child.Preds = append(child.Preds, Edge{p, pk.i})
				ai := b.Succs[out].i
				for _, v := range child.Values {
					if v.Op != OpPhi {
						continue
					}
					v.AddArg(v.Args[ai])
				}
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(b.Controls[0].Pos, "Redirect %s based on %s", b.Controls[0].Op, p.Controls[0].Op)
				}
				changed = true
				k--
				break
			}
			ft.restore()
		}
		if len(b.Preds) == 0 && b != f.Entry {
			// 布洛克现在死了。
			b.Kind = BlockInvalid
		}
	}
	ft.restore()
	ft.cleanup(f)
	return changed
}
